home *** CD-ROM | disk | FTP | other *** search
/ IRIX Base Documentation 2001 May / SGI IRIX Base Documentation 2001 May.iso / usr / share / catman / p_man / cat3c / bsearch.z / bsearch
Encoding:
Text File  |  1998-10-20  |  13.0 KB  |  133 lines
  1.  
  2.  
  3.  
  4. bbbbsssseeeeaaaarrrrcccchhhh((((3333CCCC))))                                                        bbbbsssseeeeaaaarrrrcccchhhh((((3333CCCC))))
  5.  
  6.  
  7.  
  8. NNNNAAAAMMMMEEEE
  9.      _bbbb_ssss_eeee_aaaa_rrrr_cccc_hhhh - binary search a sorted table
  10.  
  11. SSSSYYYYNNNNOOOOPPPPSSSSIIIISSSS
  12.      _####_iiii_nnnn_cccc_llll_uuuu_dddd_eeee _<<<<_ssss_tttt_dddd_llll_iiii_bbbb_...._hhhh_>>>>
  13.  
  14.      _vvvv_oooo_iiii_dddd _****_bbbb_ssss_eeee_aaaa_rrrr_cccc_hhhh _((((_cccc_oooo_nnnn_ssss_tttt _vvvv_oooo_iiii_dddd _****_kkkk_eeee_yyyy_,,,, _cccc_oooo_nnnn_ssss_tttt _vvvv_oooo_iiii_dddd _****_bbbb_aaaa_ssss_eeee_,,,, _ssss_iiii_zzzz_eeee______tttt _nnnn_eeee_llll_,,,,
  15.          _ssss_iiii_zzzz_eeee______tttt _ssss_iiii_zzzz_eeee_,,,, _iiii_nnnn_tttt _((((_****_cccc_oooo_mmmm_pppp_aaaa_rrrr_))))_((((_cccc_oooo_nnnn_ssss_tttt _vvvv_oooo_iiii_dddd _****_,,,, _cccc_oooo_nnnn_ssss_tttt _vvvv_oooo_iiii_dddd _****_))))_))))_;;;;
  16.  
  17. DDDDEEEESSSSCCCCRRRRIIIIPPPPTTTTIIIIOOOONNNN
  18.      _bbbb_ssss_eeee_aaaa_rrrr_cccc_hhhh is a binary search routine generalized from Knuth (6.2.1)
  19.      Algorithm B.  It returns a pointer into a table (an array) indicating
  20.      where a datum may be found or a null pointer if the datum cannot be
  21.      found.  The table must be previously sorted in increasing order according
  22.      to a comparison function pointed to by _c_o_m_p_a_r.  _k_e_y points to a datum
  23.      instance to be sought in the table.  _b_a_s_e points to the element at the
  24.      base of the table.  _n_e_l is the number of elements in the table.  _s_i_z_e is
  25.      the number of bytes in each element.  The function pointed to by _c_o_m_p_a_r
  26.      is called with two arguments that point to the elements being compared.
  27.      The function must return an integer less than, equal to, or greater than
  28.      0 as accordingly the first argument is to be considered less than, equal
  29.      to, or greater than the second.
  30.  
  31. EEEEXXXXAAAAMMMMPPPPLLLLEEEE
  32.      The example below searches a table containing pointers to nodes
  33.      consisting of a string and its length.  The table is ordered
  34.      alphabetically on the string in the node pointed to by each entry.
  35.  
  36.      This program reads in strings and either finds the corresponding node and
  37.      prints out the string and its length, or prints an error message.
  38.  
  39.           _####_iiii_nnnn_cccc_llll_uuuu_dddd_eeee _<<<<_ssss_tttt_dddd_iiii_oooo_...._hhhh_>>>>
  40.           _####_iiii_nnnn_cccc_llll_uuuu_dddd_eeee _<<<<_ssss_tttt_dddd_llll_iiii_bbbb_...._hhhh_>>>>
  41.           _####_iiii_nnnn_cccc_llll_uuuu_dddd_eeee _<<<<_ssss_tttt_rrrr_iiii_nnnn_gggg_...._hhhh_>>>>
  42.  
  43.           _ssss_tttt_rrrr_uuuu_cccc_tttt _nnnn_oooo_dddd_eeee _{{{{            _////_**** _tttt_hhhh_eeee_ssss_eeee _aaaa_rrrr_eeee _ssss_tttt_oooo_rrrr_eeee_dddd _iiii_nnnn _tttt_hhhh_eeee _tttt_aaaa_bbbb_llll_eeee _****_////
  44.                _cccc_hhhh_aaaa_rrrr _****_ssss_tttt_rrrr_iiii_nnnn_gggg_;;;;
  45.                _iiii_nnnn_tttt _llll_eeee_nnnn_gggg_tttt_hhhh_;;;;
  46.           _}}}}_;;;;
  47.           _ssss_tttt_aaaa_tttt_iiii_cccc _ssss_tttt_rrrr_uuuu_cccc_tttt _nnnn_oooo_dddd_eeee _tttt_aaaa_bbbb_llll_eeee_[[[[_]]]] _====  _////_**** _tttt_aaaa_bbbb_llll_eeee _tttt_oooo _bbbb_eeee _ssss_eeee_aaaa_rrrr_cccc_hhhh_eeee_dddd _****_////
  48.           _{{{{
  49.                _{{{{ _""""_aaaa_ssss_pppp_aaaa_rrrr_aaaa_gggg_uuuu_ssss_""""_,,,, _1111_0000 _}}}}_,,,,
  50.                _{{{{ _""""_bbbb_eeee_aaaa_nnnn_ssss_""""_,,,, _6666 _}}}}_,,,,
  51.                _{{{{ _""""_tttt_oooo_mmmm_aaaa_tttt_oooo_""""_,,,, _7777 _}}}}_,,,,
  52.                _{{{{ _""""_wwww_aaaa_tttt_eeee_rrrr_mmmm_eeee_llll_oooo_nnnn_""""_,,,, _1111_1111 _}}}}_,,,,
  53.           _}}}}_;;;;
  54.  
  55.           _mmmm_aaaa_iiii_nnnn_((((_))))
  56.           _{{{{
  57.                _ssss_tttt_rrrr_uuuu_cccc_tttt _nnnn_oooo_dddd_eeee _****_nnnn_oooo_dddd_eeee______pppp_tttt_rrrr_,,,, _nnnn_oooo_dddd_eeee_;;;;
  58.                _////_**** _rrrr_oooo_uuuu_tttt_iiii_nnnn_eeee _tttt_oooo _cccc_oooo_mmmm_pppp_aaaa_rrrr_eeee _2222 _nnnn_oooo_dddd_eeee_ssss _****_////
  59.                _ssss_tttt_aaaa_tttt_iiii_cccc _iiii_nnnn_tttt _nnnn_oooo_dddd_eeee______cccc_oooo_mmmm_pppp_aaaa_rrrr_eeee_((((_cccc_oooo_nnnn_ssss_tttt _vvvv_oooo_iiii_dddd _****_,,,, _cccc_oooo_nnnn_ssss_tttt _vvvv_oooo_iiii_dddd _****_))))_;;;;
  60.  
  61.  
  62.  
  63.                                                                         PPPPaaaaggggeeee 1111
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70. bbbbsssseeeeaaaarrrrcccchhhh((((3333CCCC))))                                                        bbbbsssseeeeaaaarrrrcccchhhh((((3333CCCC))))
  71.  
  72.  
  73.  
  74.               _cccc_hhhh_aaaa_rrrr _ssss_tttt_rrrr______ssss_pppp_aaaa_cccc_eeee_[[[[_2222_0000_]]]]_;;;;   _////_**** _ssss_pppp_aaaa_cccc_eeee _tttt_oooo _rrrr_eeee_aaaa_dddd _ssss_tttt_rrrr_iiii_nnnn_gggg _iiii_nnnn_tttt_oooo _****_////
  75.  
  76.                _nnnn_oooo_dddd_eeee_...._ssss_tttt_rrrr_iiii_nnnn_gggg _==== _ssss_tttt_rrrr______ssss_pppp_aaaa_cccc_eeee_;;;;
  77.                _wwww_hhhh_iiii_llll_eeee _((((_ssss_cccc_aaaa_nnnn_ffff_((((_""""_%%%%_2222_0000_ssss_""""_,,,, _nnnn_oooo_dddd_eeee_...._ssss_tttt_rrrr_iiii_nnnn_gggg_)))) _!!!!_==== _EEEE_OOOO_FFFF_)))) _{{{{
  78.                     _nnnn_oooo_dddd_eeee______pppp_tttt_rrrr _==== _bbbb_ssss_eeee_aaaa_rrrr_cccc_hhhh_(((( _&&&&_nnnn_oooo_dddd_eeee_,,,,
  79.                             _tttt_aaaa_bbbb_llll_eeee_,,,, _ssss_iiii_zzzz_eeee_oooo_ffff_((((_tttt_aaaa_bbbb_llll_eeee_))))_////_ssss_iiii_zzzz_eeee_oooo_ffff_((((_ssss_tttt_rrrr_uuuu_cccc_tttt _nnnn_oooo_dddd_eeee_))))_,,,,
  80.                             _ssss_iiii_zzzz_eeee_oooo_ffff_((((_ssss_tttt_rrrr_uuuu_cccc_tttt _nnnn_oooo_dddd_eeee_))))_,,,, _nnnn_oooo_dddd_eeee______cccc_oooo_mmmm_pppp_aaaa_rrrr_eeee_))))_;;;;
  81.                     _iiii_ffff _((((_nnnn_oooo_dddd_eeee______pppp_tttt_rrrr _!!!!_==== _NNNN_UUUU_LLLL_LLLL_)))) _{{{{
  82.                          _((((_vvvv_oooo_iiii_dddd_)))) _pppp_rrrr_iiii_nnnn_tttt_ffff_((((_""""_ssss_tttt_rrrr_iiii_nnnn_gggg _==== _%%%%_2222_0000_ssss_,,,, _llll_eeee_nnnn_gggg_tttt_hhhh _==== _%%%%_dddd_\\\\_nnnn_""""_,,,,
  83.                               _nnnn_oooo_dddd_eeee______pppp_tttt_rrrr_----_>>>>_ssss_tttt_rrrr_iiii_nnnn_gggg_,,,, _nnnn_oooo_dddd_eeee______pppp_tttt_rrrr_----_>>>>_llll_eeee_nnnn_gggg_tttt_hhhh_))))_;;;;
  84.                     _}}}} _eeee_llll_ssss_eeee _{{{{
  85.                          _((((_vvvv_oooo_iiii_dddd_))))_pppp_rrrr_iiii_nnnn_tttt_ffff_((((_""""_nnnn_oooo_tttt _ffff_oooo_uuuu_nnnn_dddd_:::: _%%%%_2222_0000_ssss_\\\\_nnnn_""""_,,,, _nnnn_oooo_dddd_eeee_...._ssss_tttt_rrrr_iiii_nnnn_gggg_))))_;;;;
  86.                     _}}}}
  87.                _}}}}
  88.                _rrrr_eeee_tttt_uuuu_rrrr_nnnn_((((_0000_))))_;;;;
  89.           _}}}}
  90.  
  91.           _////_**** _rrrr_oooo_uuuu_tttt_iiii_nnnn_eeee _tttt_oooo _cccc_oooo_mmmm_pppp_aaaa_rrrr_eeee _tttt_wwww_oooo _nnnn_oooo_dddd_eeee_ssss _bbbb_aaaa_ssss_eeee_dddd _oooo_nnnn _aaaa_nnnn  _****_////
  92.           _////_**** _aaaa_llll_pppp_hhhh_aaaa_bbbb_eeee_tttt_iiii_cccc_aaaa_llll _oooo_rrrr_dddd_eeee_rrrr_iiii_nnnn_gggg _oooo_ffff _tttt_hhhh_eeee _ssss_tttt_rrrr_iiii_nnnn_gggg _ffff_iiii_eeee_llll_dddd _****_////
  93.           _ssss_tttt_aaaa_tttt_iiii_cccc _iiii_nnnn_tttt
  94.           _nnnn_oooo_dddd_eeee______cccc_oooo_mmmm_pppp_aaaa_rrrr_eeee_((((_cccc_oooo_nnnn_ssss_tttt _vvvv_oooo_iiii_dddd _****_nnnn_oooo_dddd_eeee_1111_,,,, _cccc_oooo_nnnn_ssss_tttt _vvvv_oooo_iiii_dddd _****_nnnn_oooo_dddd_eeee_2222_))))
  95.           _{{{{
  96.                _rrrr_eeee_tttt_uuuu_rrrr_nnnn _((((_ssss_tttt_rrrr_cccc_mmmm_pppp_((((
  97.                          _((((_((((_cccc_oooo_nnnn_ssss_tttt _ssss_tttt_rrrr_uuuu_cccc_tttt _nnnn_oooo_dddd_eeee _****_))))_nnnn_oooo_dddd_eeee_1111_))))_----_>>>>_ssss_tttt_rrrr_iiii_nnnn_gggg_,,,,
  98.                          _((((_((((_cccc_oooo_nnnn_ssss_tttt _ssss_tttt_rrrr_uuuu_cccc_tttt _nnnn_oooo_dddd_eeee _****_))))_nnnn_oooo_dddd_eeee_2222_))))_----_>>>>_ssss_tttt_rrrr_iiii_nnnn_gggg_))))_))))_;;;;
  99.           _}}}}
  100.  
  101. SSSSEEEEEEEE AAAALLLLSSSSOOOO
  102.      _hhhh_ssss_eeee_aaaa_rrrr_cccc_hhhh(3C), _llll_ssss_eeee_aaaa_rrrr_cccc_hhhh(3C), _qqqq_ssss_oooo_rrrr_tttt(3C), _tttt_ssss_eeee_aaaa_rrrr_cccc_hhhh(3C).
  103.  
  104. DDDDIIIIAAAAGGGGNNNNOOOOSSSSTTTTIIIICCCCSSSS
  105.      A null pointer is returned if the key cannot be found in the table.
  106.  
  107. NNNNOOOOTTTTEEEESSSS
  108.      The pointers to the key and the element at the base of the table should
  109.      be of type pointer-to-_e_l_e_m_e_n_t.
  110.  
  111.      The comparison function need not compare every byte, so arbitrary data
  112.      may be contained in the elements in addition to the values being
  113.      compared.
  114.  
  115.      If the number of elements in the table is less than the size reserved for
  116.      the table, _n_e_l should be the lower number.
  117.  
  118.  
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128.  
  129.                                                                         PPPPaaaaggggeeee 2222
  130.  
  131.  
  132.  
  133.